package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class _146_LruCache {
    public static void main(String[] args) {
        LRUCache cache = new _146_LruCache().new LRUCache(2);
        cache.put(2, 1);
        cache.put(2, 2);
        int i = cache.get(2);
        System.out.println(i);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class LRUCache {
        int capacity;
        int sz;
        Map<Integer, Node> map = new HashMap<>();
        Node head, tail;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.sz = 0;
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            Node node = map.get(key);
            delete(node);
            addToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                delete(node);
                node.value = value;
                addToHead(node);

                // 下面创建 newNode 的速度会更慢
                // Node newNode = new Node(key, value);
                // addToHead(newNode);
                // map.put(key, newNode);
                return;
            }
            if (sz == capacity) {
                Node node = tail.prev;
                delete(node);
                map.remove(node.key);
                sz--;
            }
            Node newNode = new Node(key, value);
            addToHead(newNode);
            map.put(key, newNode);
            sz++;
        }

        private void delete(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void addToHead(Node node) {
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
            node.prev = head;
        }

        class Node {
            int key;
            int value;
            Node prev;
            Node next;

            Node(int key, int value) {
                this.key = key;
                this.value = value;
                prev = null;
                next = null;
            }
        }
    }

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)

}